package cn.lintcode;

import java.util.List;

/**
 * <h2>链表插入排序</h2>
 * <p>lintcode173题</p>
 * <p>将乱序的链表排序从小到大排序后输出</p>
 * 这个是真的不应该画如此多的时间,对指针,链表这个操作比较差
 * @author tianxx7
 * Created by seth on 2020/5/22
 */
public class InsertSortList {
    public static ListNode solute(ListNode head){
        if (null == head || null == head.next) {
            return head;
        }
        ListNode new_head = new ListNode(Integer.MIN_VALUE);
        while (null != head) {
            ListNode node = head;
            head = head.next;
            ListNode cur = new_head.next;
            ListNode pre = new_head;
            while (null != pre) {
                if (null == cur || node.val <= cur.val){
                    pre.next = node;
                    node.next = cur;
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
        return new_head.next;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        ListNode node0 = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node3;
        node3.next = node2;
        node2.next = node0;
        ListNode solute = solute(node1);
        while (solute != null) {
            System.out.print(solute.val + "->");
            solute = solute.next;
        }
        System.out.println("null");
    }
}


